from collections import deque


def find_roots(node):
    '''Walk the graph backwards, starting at target node, returning a
    list of all root nodes.

    Root Nodes are Nodes with no `source` Nodes.'''

    def walk(node, roots):
        if not node.source:
            roots.append(node)
        else:
            for n in node.source:
                roots = walk(n, roots)

        return roots

    return walk(node, [])

def build(self, target):
    '''Build a given target.

    Args:
      * target: The target ``Node`` to build.
    '''

    # cache.load()

    run_list = find_roots(target)
    while run_list:
        node = run_list.pop()

        try:
            if node.signature() != cache[node.id()]:
                node.dirty = True
                cache[node.id()] = node.signature()
        except KeyError:
            cache[node.id()] = node.signature()

        if node.dirty:
            if not node.execute():
                raise Error('Oh noes!')

            node.dirty = False

            for n in node.targets:
                n.dirty = True
                if no_dirty_sources(n):
                    run_list.append(n)

    cache.store()
